package com.lei.leetcode;

/**
 * @Author LeiXiaoLei
 * @Date 2022/9/3 11:05
 * @Version 1.0
 */
public class S_1147 {

    private long MOD = (long) (1e9 + 7);
    long[] pow26;

    public int longestDecomposition(String text) {
        pow26 = new long[text.length()];
        pow26[0] = 1;
        for (int i = 1; i < text.length(); i++) {
            pow26[i] = pow26[i - 1] * 26 % MOD;
        }
        return solve(text, 0, text.length() - 1);
    }

    private int solve(String s, int l, int r) {
        if (l > r) return 0;
        long preHash = 0, postHash = 0;
        for (int i = l, j = r; i < j; i++, j--) {
            preHash = ((preHash * 26) + (s.charAt(i) - 'a')) % MOD;
            postHash = ((s.charAt(j) - 'a') * pow26[r - j] + postHash) % MOD;
            if (preHash == postHash && equal(s, l, i, j, r))
                return 2 + solve(s, i + 1, j - 1);
        }
        return 1;
    }

    private boolean equal(String s, int l1, int r1, int l2, int r2) {
        for (int i = l1, j = l2; i <= r1 && j <= r2; i++, j++) {
            if (s.charAt(i) != s.charAt(j)) return false;
        }
        return true;
    }

//    private int solve(String s, int l, int r) {
//        if (l > r) return 0;
//
//        for (int i = l, j = r; i < j; i++, j--) {
//            if (equal(s, l, i, j, r))
//                return 2 + solve(s, i + 1, j - 1);
//        }
//        return 1;
//    }
//
//    private boolean equal(String s, int l1, int r1, int l2, int r2) {
//        for (int i = l1, j = l2; i <= r1 && j <= r2; i++, j++) {
//            if (s.charAt(i) != s.charAt(j)) return false;
//        }
//        return true;
//    }
}
